今天讓我們來聊聊在做搜尋或推薦系統絕對不可或缺的 Vector Search 演算法。

我們在前面有提過 Netflix 的 in-video search，讓用戶透過文字搜尋影片中的特定時刻。這些文字和圖片會被轉成 embeddings，並儲存在 vector database 中，以利於進行相似度搜尋。另外，在介紹 Netflix 的 Marken Platform 時，也有介紹到他們的「語義搜尋」功能，將用戶的搜尋內容轉成向量，進而比對其他向量，找到文意相近的內容。這代表 Marken 平台可能使用 vector database 來儲存和搜尋這些文字向量。

Spotify 也同樣利用 vector database 處理其龐大的音樂和 Podcast 資料庫，例如在我上次參賽時介紹過 Spotify 會用 NLP 幫助 Podcast 搜尋，或是建立「每週新發現」的歌單時，也要從資料庫中找到用戶可能會喜歡的歌單。這些應用都顯示 vector database 的重要性。

為此，Facebook 開發 FAISS（Facebook AI Similarity Search） 以助於有效率地進行相似度搜尋（similarity search）以及進行 dense vectors 的 clustering。
而 Spotify 在 2013 年建立 Annoy 來進行 nearest neighbor search，用在他們的音樂推薦系統上。不過，經過 10 年來的技術不斷進步，Annoy 的表現僅居於中位，因此 Spotify 又開發了 Voyager。相較於 Annoy，Voyager 的速度提升超過十倍，準確度提升 50%，記憶體使用量比 Annoy 少四倍。

另外，這世界上還有好多好多好多其他的 nearest neighbor search 演算法，大家可以參考這個 GitHub repo 的比較。

好了，談了這麼多背景，現在讓我們來實際試用看看吧！

Faiss & Voyager & Annoy 的用法

生成數據

# 生成數據
num_vectors = 10000
dim = 128
k = 5  # 要找最相似的前五名的向量

np.random.seed(1234)             # 固定 random seed

data = np.random.rand(num_vectors, dim).astype(np.float32)   # 資料庫的數據
query = np.random.rand(dim).astype(np.float32)               # 要 query 的向量

FAISS

import faiss

# 加入數據
index = faiss.IndexFlatL2(dim)
index.add(data)

# 搜尋數據
D, I = index.search(query, k)

Voyager

from voyager import Index, Space

index = Index(Space.Cosine, num_dimensions=dim)
index.add_items(data, np.arange(len(data)))
results = index.query(query, k)

• Index(space, num_dimensions, M, ef_construction, random_seed, max_elements) 可以設定的參數
  • space：用來計算向量之間距離的空間，通常使用 Space.Cosine，也可以使用 Space.Euclidean 或 Space.InnerProduct。
  • num_dimensions：加到此 index 中的每個向量的維度，index 中的每個向量的維度都必須相同。
  • M：樹中 nodes 之間的連接數，M 越大 則 precision 越高，但是會佔用更多的內存。在 index 初始化後無法更改。預設值是 12。
  • ef_construction：插入新向量時搜尋的向量數量，較大的值會讓 index 的建構變慢，但會提高 recall。在 index 初始化後無法更改。
  • max_elements：index 在建構時的最大數量，不過 index 的大小是可以被調整的（利用 add_item() 或 add_items()），因此此值只有在事先知道要添加到 index 的數量時有用。

Annoy

index = AnnoyIndex(dim, 'angular')
for i, v in enumerate(data):
    index.add_item(i, v)
index.build(10)  # 10 trees
results = index.get_nns_by_vector(query, k)

• AnnoyIndex(f, metric)：建立用來讀寫跟存取 vector 的 index，metric 可以是 angular、 euclidean、manhattan、hamming 或是 dot。
• index.build(n, n_jobs=-1)：會構建一個包含 n 棵樹的森林，增加樹的數量可以在查詢時提高 precision。在使用 build 之後，不能再添加任何項目。n_jobs 用來指定構建樹的 threads 數量，n_jobs=-1 會使用所有可用的 CPU。

Sanity check

FAISS

D, I = index.search(data[:5], k)   # sanity check，確認建立的沒有問題

print(I)  # 前 k 名的 index

# 每一個 row 代表每一個 query 最相似的向量 index，因為我們是用 data 當作 query 來做 sanity check，因此每個 row 的第一名都是他自己
"""
[[   0 6937  894 2879 6025]
 [   1 9400 3632 4993 1793]
 [   2 8040 8421 2851 4451]
 [   3 5553 4897 8394 8554]
 [   4 2337 2570 7036 7695]]
"""

print(D)  # 前 k 名的 distances

# 每一個 row 代表每一個 query 最相似的向量 index，因為我們是用 data 當作 query 來做 sanity check，因此每個 row 的第一名都是他自己
"""
[[ 0.        13.615374  13.877062  14.51059   14.552374 ]
 [ 0.        13.31744   14.096954  14.648132  14.8271055]
 [ 0.        15.033799  15.180595  15.2626505 15.426672 ]
 [ 0.        15.207937  15.682687  15.758978  15.852301 ]
 [ 0.        14.746198  15.029176  15.100805  15.411009 ]]
 """

Voyager
Voyager 的結果出乎意料，前三個向量有找到自己，但第四跟第五個竟然不是，也甚至不在前五名。

from voyager import Index, Space

index = Index(Space.Cosine, num_dimensions=dim)
index.add_items(data, np.arange(len(data)))
results = index.query(data[:5], k)

print(results[0])  # index
"""
[[   0 6937 7333 2879  894]
 [   1 9400 3632 4993 2712]
 [   2  502 3292 8040 4451]
 [5160 8129 8822 2372 2311]
 [2206 2570 7583   42 2624]]
"""

print(results[1])  # distance
"""
[[0.0000000e+00 1.5152103e-01 1.5843570e-01 1.5846097e-01 1.6251564e-01]
 [0.0000000e+00 1.4776921e-01 1.6197705e-01 1.6659707e-01 1.6884655e-01]
 [2.3841858e-07 1.6721964e-01 1.6740054e-01 1.6969365e-01 1.6996145e-01]
 [1.8063033e-01 1.8114495e-01 1.8368667e-01 1.8695951e-01 1.8849480e-01]
 [1.8391919e-01 1.9370306e-01 1.9724798e-01 1.9776464e-01 2.0532006e-01]]
"""

如果將 index 3 和 5160 的距離印出來，3 和 3 自己的距離的確是 0

print(index.get_distance(data[3], data[3]))      # 0.0
print(index.get_distance(data[3], data[5160]))   # 0.18063032627105713

這是一個有趣的發現，我自己也很驚訝。不過也顯示出，Voyager 如同大多數 ANN（Approximate Nearest Neighbor）算法一樣，為了提高搜尋速度，可能會犧牲一些精確度，不一定會使用整個 vector 進行比對。

我們來調整一下建立 index 的參數，我把 M 調整到 18 就正常了，不過 index 的建立時間，以及搜尋時間，都有些微提升，顯示出提升精度，就會降低搜尋速度。

from voyager import Index, Space
import time

index = Index(Space.Cosine, num_dimensions=dim, M=18)

start_time = time.time()
index.add_items(data, np.arange(len(data)))
build_time = time.time() - start_time

start_time = time.time()
results = index.query(data[:5], k)
search_time = time.time() - start_time

print(results[0])
"""
[[   0 6937 8654 7333 2879]
 [   1 9400 3632 4993 2712]
 [   2  502 3292 8040 4451]
 [   3 3140 5553 8474 2003]
 [   4 2206 2337 2282   42]]
"""
print(f'build_time = {build_time:.4f}, search_time = {search_time:.6f}')
# build_time = 4.3291, search_time = 0.000824
# 當 M=12 時，build_time = 2.4539, search_time = 0.000636

Annoy
使用預設值的 Annoy 沒有發現這個問題，我們就不特別把結果貼上來啦！

三個的效率比較

最後是不專業的三個演算法的效率比較時間，我測試的參數如下，實驗的程式碼放在最後面的附錄。

測試資料集

• 資料量：50000 個
• 向量：256 維
• 搜索前五相似的

結果

• Voyager

  • index 建立時間：58.8216 秒
  • 搜尋時間：0.000252 秒

• Annoy

  • index 建立時間：2.1305 秒
  • 搜尋時間：0.000137 秒

• FAISS

  • index 建立時間：0.0426 秒
  • 搜尋時間：0.006071 秒

結果 Voyager 的 index 建立時間明顯比其他兩者慢很多，雖然搜尋時間有比 FAISS 快，但怎麼好像也沒有比自家的 Annoy 快（摸下巴）。

❗️❗️❗️
但！是！這只是我隨機生成一筆實驗數據，統一在 Google Colab 的 CPU 上執行，完全沒有比較其他資料儲存、記憶體佔用，或是跑在 GPU 的時間！所以不是最準確跟完整的比較！請大家就是看看當參考就好！
❗️❗️❗️

好的，以上就是三種 vector search 的算法介紹跟比較啦！
到底孰優孰劣，我也是沒有一個確切答案，還是看大家的需求以及官方文件再做選擇。
或是大家有什麼想法跟實際使用經驗的話，也非常歡迎跟我分享！

謝謝讀到最後的你，如果喜歡這系列，別忘了按下喜歡和訂閱，才不會錯過最新更新。
如果有任何問題想跟我聊聊，或是想看我分享的其他內容，也歡迎到我的 Instagram（@data.scientist.min） 逛逛！
我們明天見！

Reference

• https://github.com/facebookresearch/faiss.git
• https://github.com/spotify/annoy.git
• https://github.com/spotify/voyager.git

Supplements

• 效率比較實驗

import numpy as np
import time
from voyager import Index, Space
from annoy import AnnoyIndex
import faiss

def benchmark_voyager(data, query, k):
    # Create an empty Index object that can store vectors:
    index = Index(Space.Euclidean, num_dimensions=dim)  ## 可以選 Euclidean、InnerProduct 和 Cosine
    start_time = time.time()
    index.add_items(data, np.arange(len(data)))
    build_time = time.time() - start_time
    
    start_time = time.time()
    results = index.query(query, k)
    search_time = time.time() - start_time
    return build_time, search_time

def benchmark_annoy(data, query, k):
    index = AnnoyIndex(dim, 'angular')
    start_time = time.time()
    for i, v in enumerate(data):
        index.add_item(i, v)
    index.build(10)  # 10 trees
    build_time = time.time() - start_time
    
    start_time = time.time()
    results = index.get_nns_by_vector(query, k)
    search_time = time.time() - start_time
    return build_time, search_time

def benchmark_faiss(data, query, k):
    index = faiss.IndexFlatIP(dim)
    start_time = time.time()
    index.add(data)
    build_time = time.time() - start_time
    
    start_time = time.time()
    D, I = index.search(query.reshape(1, -1), k)
    search_time = time.time() - start_time
    return build_time, search_time

# 設置參數
num_vectors = 50000
dim = 256
k = 5
np.random.seed(1234)             # 固定 random seed

# 生成數據
data = np.random.rand(num_vectors, dim).astype(np.float32)   # 資料庫的數據
query = np.random.rand(dim).astype(np.float32)

# 運行基準測試
print(f"測試參數: {num_vectors} 向量, {dim} 維度, 搜索 top {k}")

for name, benchmark_func in [
    ("Voyager", benchmark_voyager),
    ("Annoy", benchmark_annoy),
    ("FAISS", benchmark_faiss),
    # ("ScaNN", benchmark_scann)
]:
    build_time, search_time = benchmark_func(data, query, k)
    print(f"{name}:")
    print(f"  index 建立時間：{build_time:.4f} 秒")
    print(f"  搜尋時間：{search_time:.6f} 秒")
    print()